
class Solution {
    private int mod = 1_000_000_007;
    //记忆化
    private int dfs(int n , int zero , int one, int [] mem){ 
        if (n == 0){ 
            return 1;
        }
        if (n < 0){ 
            return 0;
        }
        if (mem[n] != -1) { 
            return mem[n];
        }
        return mem[n] = ((dfs(n - zero, zero, one, mem)) % mod + dfs(n - one, zero, one, mem) % mod) % mod;
    }
    public int countGoodStrings(int low, int high, int zero, int one) {
        int mem[] = new int[high + 1];
        Arrays.fill(mem, -1);

        int ans = 0;
        for (int i = low; i <= high; i++){ 
            ans = (ans + dfs(i, zero, one, mem)) % mod;
        }
        return ans;
    }
    //dp
    private static final int mod = 1_000_000_007;
    public int countGoodStrings(int low, int high, int zero, int one) {
        int []dp = new int[high + 1];
        // Arrays.fill(dp, 0);
        dp[0] = 1;
        int ans = 0;
        for (int i = 1; i <= high; i++){ 
            if (i >= zero)
                dp[i] = dp[i - zero];
            if (i >= one)
                dp[i] = (dp[i] + dp[i - one]) % mod;
            if (i >= low)
                ans = (ans + dp[i]) % mod;
        }
        return ans;
    }

}
